/*
Given two word of equal length that are in dictionary , write a method to transform one word into another word by changing only one letter at a time. The new word you get in each step must be in the dictionary.
Example:
I: DAMP,LIKE
O: DAMP-> LAMP-> LIMP -> LIME -> LIKE
*/
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;


/* using dfs */
bool transfer(string &src, string &dst, set<string> &dict, vector<string> &myStr, map<string, bool> &mp)
{
    if (src == dst) {
	for (int i = 0; i < myStr.size(); i++)
	    cout << myStr[i] << " ";
	cout << endl;
        return true;
    }

    for (int i = 0; i < src.size(); i++) {
        for (int j = 0; j < 26; j++) {
            char ch = 'A' + j;
            string str = src.substr(0,i) + ch + src.substr(i+1, src.size() - i -1);
            if (str == src || dict.count(str) == 0) continue;
            if (mp[str] == true) continue;
	    myStr.push_back(str);
            mp[str] = true;
	    if (transfer(str, dst, dict, myStr, mp)) return true;
            mp[str] = false;
            myStr.pop_back();	
	}
    }
    return false;
}

void transfer2(string &str, string &dst, set<string> &dict)
{
    set<string> Visited;
    map<string, string> backtrackMap;
    queue<string> que;
    Visited.insert(str);
    que.push(str);

    while(!que.empty()) {
	string top = que.front();
	que.pop();

	string pre = top;
	for (int i = 0; i < top.size(); i++) {
	    top = pre;  //recover 
	    for (char c = 'A'; c <= 'Z'; c++) {
		top[i] = c;
		if (Visited.count(top) == 0 && dict.count(top) != 0) {
		    Visited.insert(top);
		    backtrackMap[top] = pre;
		    que.push(top);
		}
		if (top == dst) {
		    while(dst != str) {
		        cout << dst << " ";
		        dst = backtrackMap[dst];
		    }
		    return;
		}

	    }
	}
    }

}


int main(int argc, char **argv)
{
    string src = "DAMP";
    string dst = "LIKE";
    set<string> dict;
    dict.insert("LAMP");
    dict.insert("LIMP");
    dict.insert("LIME");
    dict.insert("LIKE");
    vector<string> myStr;
    myStr.push_back(src);
    map<string, bool> mp;
    transfer(src, dst, dict, myStr, mp);
    transfer2(src, dst, dict);
}
